96. Unique Binary Search Trees — Medium

Given an integer n, return the number of structurally unique BST' s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3

Output: 5

Example 2:

Input: n = 1

Output: 1

Constraints:

• 1 <= n <= 19

---

Key take away

二叉搜索树

以1 ... n 为节点组成的二叉搜索树，不同的树在于根结点的不同和左右子树的不同

分治递归

将每个节点的左右子树的情况分别进行讨论

---

思路

对于n个节点，除去根节点之后，每个节点的左右子树的分别有如下数量的节点：

(0, n - 1), (1, n - 2), (2, n - 3), ....(n - 1, 0)

所以，当根节点为 i 时，左子树 A 的节点数量为 i - 1 ，右子树 B 的节点数量为 n - i

最后递归，并将左子树 A 和右子树 B 的结果相乘即可。

易错点

⚠️不要在计算 dp[i] 时将其初始化为1

用一个helper function来计算 i 个节点所能拥有的子树数量 —> 空间复杂度高，可优化

代码

class Solution {

public:

vector<int> visited;

int numTrees(int n) {

// assign vector

visited.assign(n + 1, 0);

// if 0 node: 1(since will be multiplied with dp(n - i - 1))

visited[0] = 1;

// for n nodes

if (n <= 1) return 1;

return dp(n);

}

int dp(int n) {

// last node(boundary)

if (visited[n]) return visited[n];

// record current answer(number of unique child trees)

int ans = 0;

for (int i = 0; i < n; ++i) {

// for each child node, get number of unique tress it can have

ans += dp(i) * dp(n - i - 1);

}

return visited[n] = ans;

}

};

Runtime: 0 ms, 100% Memory Usage: 6.2 MB, 6.12%

---

优化

用一个数组储存dp(i)的值：

int numTrees(int n) {

vector<int> dp(n + 1, 0);

dp[0]=1;

dp[1]=1;

for(int i=2;i<=n;i++){

int left=0;

int right=i-1;

while(left<=i-1){

dp[i]+= dp[left]*dp[right];

left++;

right--;

}

}

return dp[n];

}

双指针

这里用双指针来记录当前位置，也可以使用第一种解法里的单指针 (dp[i] += dp[i] + dp[n - i - 1], where n is current index of dp)

单指针代码：

int numTrees(int n) {

vector<int> dp(n + 1, 0);

dp[0]=1;

dp[1]=1;

for(int i=2;i<=n;i++){

int cur = 0;

while(cur < i){

dp[i] += dp[cur] * dp[i - cur - 1];

cur++;

}

}

return dp[n];

}

Runtime: 0 ms, 100% Memory Usage: 6 MB, 21.53 %

Emmm 为什么内存没有被优化多少呢:❓